package _11_整理题目._6_模拟设计._多数之和;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/4sum/
 *
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
 * 请你找出并返回满足下述条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
 *      a、b、c 和 d 互不相同
 *      nums[a] + nums[b] + nums[c] + nums[d] == target
 *
 */
public class _041_四数之和 {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res  =  new ArrayList<>();
        int n = nums.length;
        if (n < 4) return new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j-1]) continue;

                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while(left < right && nums[left+1] == nums[left]) left++;
                        while (left < right && nums[right-1] == nums[right]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }

    @Test
    public void main() {
        int[] nums = {1,0,-1,0,-2,2};
        List<List<Integer>> res = fourSum(nums, 0);
        for (List<Integer> re : res) {
            System.out.println(re);
        }
    }

}
